量子计算时代的机器学习

人工智能和量子信息

在讲量子机器学习之前我们先来八卦一下人工智能和量子信息。1956，达特茅斯，十位大牛聚集于此，麦卡锡（John McCarthy）给这个活动起了个别出心裁的名字：“人工智能夏季研讨会”（Summer Research Project on Artificial Intelligence），现在被普遍认为是人工智能的起点。AI的历史是非常曲折的，从符号派到联结派，从逻辑推理到统计学习，从经历70年代和80年代两次大规模的政府经费削减，到90年代开始提出神经网络，默默无闻直到2006年Hinton提出深层神经网络的层级预训练方法，从专注于算法到李飞飞引入ImageNet，大家开始注意到数据的重要性，大数据的土壤加上计算力的摩尔定律迎来了现在深度学习的火热。

量子信息的历史则更为悠久和艰难。这一切都可以归结到1935年，爱因斯坦，波多尔斯基和罗森在“Can Quantum-Mechanical Description of Physical Reality be Considered Complete?”一文中提出了EPR悖论，从而引出了量子纠缠这个概念。回溯到更早一点，1927年第五次索尔维会议，世界上最主要的物理学家聚在一起讨论新近表述的量子理论。会议上爱因斯坦和波尔起了争执，爱因斯坦用“上帝不会掷骰子”的观点来反对海森堡的不确定性原理，而玻尔反驳道，“爱因斯坦，不要告诉上帝怎么做”。这一论战持续了很多年，伴随着量子力学的发展，直到爱因斯坦在1955年去世。

爱因斯坦直到去世也还一直坚持这个世界没有随机性这种东西，所有的物理规律都是确定性的，给定初态和演化规律，物理学家就能推算出任意时刻系统的状态。而量子力学生来就伴随了不确定性，一只猫在没测量前可以同时“生”和"死"，不具备一个确定的状态，只有测量后这只猫才具备“生”和"死"其中的一种状态，至于具体是哪一种状态量子力学只能告诉我们每一种态的概率，给不出一个确定的结果。当然，什么操作可以被称为“测量”直到现在也没有定论，必须有意识的人或者动物来观测才能称为测量吗？还是当测量系统大到某一个程度就能使系统坍缩到某一个状态？量子力学以它的极其准确的理论预测和被无数的实验所验证而出名，也以缺少一个能被我们广泛理解的诠释而“臭名昭著”。

当然，当时大部分物理学家并不太care这件事，教学的时候教授们也大多采用“Shut up and calculate"的态度（现在依旧如此），但是也有很多人被这件事深深地所困扰。Everett在1957年提出多世界诠释（many world interpretation）来反对正统的哥本哈根诠释，指出系统在未测量的时候处于多个世界，测量后系统不变，只是观察者进入了其中一个分支。最近2014年又新出一个量子贝叶斯诠释（Qbism），用贝叶斯的角度来解释，不过那都是后话了。1964年Bell提出Bell不等式，能够用实验来验证量子力学是否是局域实在论（local realism），实在论就是这个世界是独立于观察者而存在的。有实验方案后大家才开始认真考虑起这个问题，结果后来的实验，包括去年2016年比较大的实验突破，基本验证了量子力学不能同时是局域的，又是实在的。承认实在论的话我们就有了量子纠缠这种非局域（non-local）的资源。

一小块固体含的原子数目是10的23次方量级，如果要求解这么多粒子的薛定谔方程（量子力学的基本方程）基本是没有希望的（3个粒子的都已经很难了啊喂），这样就没法用计算机模拟材料，从而预测它们的性质。我们的大物理学家费曼在1982年想到既然我们想模拟的对象是quantum的，那么我们为什么不能建一个quantum的计算机来模拟呢？量子计算机就是在这样的背景下提出来的，我们的”顽童“费曼在他的晚年也都专心致力于量子计算机的研究。像经典计算机的一样，通用的量子计算模型也有很多种，其中用得最多的是量子线路（quantum circuit）模型，其他的还有像量子图灵机（quantum Turing machine），拓扑量子计算机（topological quantum computer）等等。

由于量子计算机天然具有”并行“（quantum parallelism）的特性，我们对处于量子叠加态的系统进行操作相当于同时对指数多个经典计算机操作，能够设计出比经典算法有指数加速的量子算法，其中最著名的当属1994年的Shor算法了，能够以指数的速度破解全球的加密系统，量子计算这个领域也是在那个时候火起来的。

量子机器学习

现在机器学习这么火，大家自然想知道以后20、30年人工智能会往哪个方向发展。而正如我们之前说到的，人工智能的发展离不开计算力按摩尔定律地提升，当我们把芯片做得越来越小，晶体管的尺寸越来越接近单个原子的大小，这个时候量子效应就会出现，干扰器件的正常工作，比如以前晶体管可以通过电流是否通过来表示开和关，当有量子效应后，原本不能流过的电子现在有一定的概率”隧穿“（tunnel）过去，导致晶体管没法继续工作了。所以摩尔定律会不再成立了，那我们怎么办？一个方案就是量子计算芯片，储存的对象不再是bit，而是qubit，外部设备把命令发送给芯片，芯片以量子的方式处理完信息后再把结果传出去。由于量子效应需要极低的温度（毫K量级），我们现在看到的房间那么大的量子计算机其实绝大部分是冷却装置，真正的量子的部分只有最中心的那块芯片。

说起机器学习肯定要提起神经网络，而早在1997年大家就开始陆陆续续讨论quantum neural network（QNN）的模型了，比如Gupta，Bonnell 和 Papini的文章，不过并没有取得很大的进展。2001年后大家好像就比较沉寂了，没有什么新的工作。结果这一沉寂就到了2014年，南非的一个理论物理的组开始认真地考虑这个模型，两个博士生Sinayskiy和Schuld在研究所主任Petruccione的带领下开始考虑Hopfield-type networks的quantum evolution。但是由于非线性是neural核心的一部分，而quantum evolution是unitary的（线性的），这样就有一个本质上的矛盾，所以他们提出应该考虑神经网络的开放量子演化（open quantum evolution/dissipative quantum computing），也就是考虑进环境的非线性的耗散作用[1]。他们的工作引起了比较大的关注，所以今年2017年1月，第一个量子机器学习的summer school就在南非召开（笔者本来也想去打个酱油，结果签证没办下来，哭）。

除了神经网络的量子推广，细胞自动机（automata）和康威（conway）的生命游戏（game of life）也有量子的推广。比如”quantum aspect of life“ 这本书，由大名鼎鼎的数学物理学家彭罗斯（Roger Penrose）作序。而最早的细胞自动机的量子推广早在1988年就被量子信息的奠基人之一塞林格（Zeilinger）提了出来[2]。

相比量子的理论模型，量子人工智能的算法发展则更为引人注目。最先应该提的是2009年MIT的Aram Harrow等人提出的HHL量子算法[3]，能够以指数快的速度解一个线性方程组。这个算法构成了后来2014年Seth Lloyd他们提出的量子支持向量机的基础（quantum support vector machine，QSVM）[4]。紧随其后又有众多的经典机器学习算法的量子版本被提出来了，比如量子主成分分析（Quantum principal component analysis）[5]，量子推荐系统（Quantum Recommendation Systems）[6]，贝叶斯网络上的量子推断[7]，量子增强学习（quantum reinforcement learning）[8]等等。

除了做机器学习直接的量子推广外，还有一个很重要的方向是用量子物理来解释为什么深度学习这么有效。2014年普林斯顿的两个博士生证明了卷积神经网络可以和变分重整化群可以一一映射起来[9]。MIT宇宙学教授Max Tegmark也从信息提取和重整化的角度来说明为什么深度学习需要”深“[10]。四位计算机科学家也从他们领域的角度分析了量子多体波函数，纠缠，张量网络和卷积神经网络的关系[11]。从机器学习的理论角度上来看，量子信息的理论计算机学家Ronald de Wolf从Probably Approximately Correct(PAC) learning model的量子版本来分析算法的time，query和sample的复杂度[12]。

当然除了物理对机器学习的启发，机器学习对物理的研究也有很大的突破。最广为人知的是去年2016年下半年Troyer他们组发在Science上的一篇文章，用神经网络来解决量子多体问题[13]，随后又有研究人员用玻尔兹曼机（Boltzmann machine）来做多体相变，拓扑手性态，量子控制，量子纠错码（quantum error correction），全息（holography）等等。

最后，关于量子信息和机器学习交叉领域更为细致的survey可以参考[14,15]。

本文作者：

黄金龙 南方科技大学大四本科生 

知乎号：千风者

研究方向：量子信息与相对论和凝聚态的交叉。大三时分析过纠缠在黑洞附近如何变化，也做过波色抽样（quantum supremacy的一种方案）的理论分析及经典模拟。对deep Boltzmann machine以及机器学习的理论模型比较感兴趣。

参考文献：

1）Schuld, Maria, Ilya Sinayskiy, and Francesco Petruccione. "The quest for a quantum neural network." Quantum Information Processing 13.11 (2014): 2567-2586.

2）Grössing, Gerhard, and Anton Zeilinger. "Quantum cellular automata." Complex Systems2.2 (1988): 197-208.

3）Harrow, Aram W., Avinatan Hassidim, and Seth Lloyd. "Quantum algorithm for linear systems of equations." Physical review letters 103.15 (2009): 150502.

4）Rebentrost, Patrick, Masoud Mohseni, and Seth Lloyd. "Quantum support vector machine for big data classification." Physical review letters 113.13 (2014): 130503.

5）Lloyd, Seth, Masoud Mohseni, and Patrick Rebentrost. "Quantum principal component analysis." arXiv preprint arXiv:1307.0401 (2013).

6）Kerenidis, Iordanis, and Anupam Prakash. "Quantum recommendation systems." arXiv preprint arXiv:1603.08675 (2016).

7）Low, Guang Hao, Theodore J. Yoder, and Isaac L. Chuang. "Quantum inference on Bayesian networks." Physical Review A 89.6 (2014): 062315.

8）Dong, Daoyi, et al. "Quantum reinforcement learning." IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 38.5 (2008): 1207-1220.

9）Mehta, Pankaj, and David J. Schwab. "An exact mapping between the variational renormalization group and deep learning." arXiv preprint arXiv:1410.3831 (2014).

10）Lin, Henry W., Max Tegmark, and David Rolnick. "Why does deep and cheap learning work so well?." Journal of Statistical Physics (2016): 1-25.

11）Levine, Yoav, et al. "Deep Learning and Quantum Physics: A Fundamental Bridge." arXiv preprint arXiv:1704.01552 (2017).

12）Arunachalam, Srinivasan, and Ronald de Wolf. "A survey of quantum learning theory." arXiv preprint arXiv:1701.06806 (2017).

13）Carleo, Giuseppe, and Matthias Troyer. "Solving the quantum many-body problem with artificial neural networks." Science 355.6325 (2017): 602-606.

14）Biamonte, Jacob, et al. "Quantum machine learning." arXiv preprint arXiv:1611.09347(2016).

15）Adcock, Jeremy, et al. "Advances in quantum machine learning." arXiv preprint arXiv:1512.02900 (2015).

推荐阅读

---

集智QQ群｜292641157
商务合作｜[e-mail]
投稿转载｜[e-mail]

◆ ◆ ◆

搜索公众号：集智俱乐部

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧！